package nl.utwente.eemcs.common.analysis;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingDeque;

import nl.utwente.eemcs.graph.BranchedConstruct;
import nl.utwente.eemcs.graph.Edge;
import nl.utwente.eemcs.graph.EdgeType;
import nl.utwente.eemcs.graph.Graph;
import nl.utwente.eemcs.graph.LoopConditionalNode;
import nl.utwente.eemcs.graph.LoopConstruct;
import nl.utwente.eemcs.graph.Node;

/**
 * Analyzer for finding loop constructs. The algorithm also replaces the loop constructs with LoopConstruct nodes
 * @author Evert Duipmans
 */
public class LoopConstructAnalyzer {
	/**
	 * Queue of graphs that need to be examined
	 */
	private BlockingQueue<Graph> graphQueue = new LinkedBlockingDeque<Graph>();
	
	/**
	 * List with start nodes of branches that are already examined
	 */
	private HashSet<Node> finishedStartNodes = new HashSet<Node>();
	
	/**
	 * The input graph
	 */
	private Graph inputGraph;
	
	/**
	 * Create a new instance of a loop construct analyzer
	 * @param inputGraph The input graph
	 */
	private LoopConstructAnalyzer(Graph inputGraph) {
		for (Graph g : inputGraph.getAllGraphsAndSubGraphs())
			graphQueue.add(g);
		
		this.inputGraph = inputGraph;
	}
	
	/**
	 * Analyze the graph and create loop constructs
	 * @param inputGraph Input graph
	 * @return Changed input graph
	 * @throws Exception When an error occurs during the transformation, an exception will be thrown
	 */
	public static Graph analyze(Graph inputGraph) throws Exception {
		LoopConstructAnalyzer analyzer = new LoopConstructAnalyzer(inputGraph);
		return analyzer.analyze();
	}
	
	/**
	 * Analyze graph and replace loopconstructs
	 * @return The input graph is returned, with the changes that were made by this algorithm
	 * @throws Exception When an error occurs during the transformation, an exception will be thrown
	 */
	private Graph analyze() throws Exception {
		while (!graphQueue.isEmpty()) {
			Graph g = graphQueue.take();
			findLoopNodes(g.getStartNode(), g, new ArrayList<Node>());
		}
		return inputGraph;
	}
	
	/**
	 * Walk through the graph and find the beginning of a loop construct
	 * @param currentNode Current node
	 * @param lookupGraph Graph in which the nodes are present
	 * @param visitedNodes Visited nodes list for ensuring that no inifite loops are evaluated
	 * @throws AnalysisException When an error occurs, the analysisexception is thrown
	 */
	private void findLoopNodes(Node currentNode, Graph lookupGraph, List<Node> visitedNodes) throws AnalysisException {
		if (visitedNodes.contains(currentNode))
			return;
		
		visitedNodes.add(currentNode);
		
		// In case of loop nodes, create loop constructs
		if (currentNode instanceof LoopConditionalNode && (Boolean)currentNode.getAttribute("evaluateBefore"))
			currentNode = createLoopConstructPreEvaluation((LoopConditionalNode)currentNode, lookupGraph, visitedNodes);
		else if (currentNode.hasAttribute("loopNode") && !(Boolean)currentNode.getAttribute("evaluateBefore") && !finishedStartNodes.contains(currentNode))
			currentNode = createLoopConstructPostEvaluation(currentNode, lookupGraph, visitedNodes);
		
		// Continue walking through the graph
		List<Edge> outgoingEdges = lookupGraph.getOutgoingEdges(currentNode, EdgeType.Control);
		if (outgoingEdges.size() == 1) {
			findLoopNodes(outgoingEdges.get(0).getEnd(), lookupGraph, visitedNodes);
		} else if (outgoingEdges.size() > 1)
			throw new AnalysisException("Multiple outgoing edges is not allowed in a process");
	}
	
	/**
	 * Collects nodes within the branch of a loop construct and searches for the end node of the loop
	 * @param loopNode Loop node that should be matched
	 * @param currentNode The node that is examined in the current iteration
	 * @param newGraph The new graph (inner graph of a loop construct)
	 * @param lookupGraph The original graph
	 * @param visitedNodes The visited nodes is used for ensuring that the process will not loop infinitely
	 * @return The end node of a loop
	 */
	private Node createLoopConstructContents(String loopNode, Node currentNode, Graph newGraph, Graph lookupGraph, List<Node> visitedNodes) {
		if (visitedNodes.contains(currentNode))
			return null;
		
		// Add node to graph and to visited list
		visitedNodes.add(currentNode);
		newGraph.addNode(currentNode);
		currentNode.addAttribute("repeated", true);
		
		if (currentNode instanceof LoopConditionalNode && !(Boolean)currentNode.getAttribute("evaluateBefore") && currentNode.getName().equals(loopNode))
			return currentNode;
		else if (currentNode.hasAttribute("loopNode") && (Boolean)currentNode.getAttribute("evaluateBefore") && currentNode.getAttribute("loopNode").equals(loopNode))
			return currentNode;
		else if (currentNode instanceof BranchedConstruct<?, ?>) {
			BranchedConstruct<?, ?> castedNode = (BranchedConstruct<?, ?>)currentNode;
			if ((castedNode.getStartNode().hasAttribute("loopNode") && castedNode.getStartNode().getAttribute("loopNode").equals(loopNode)) 
					|| (castedNode.getEndNode().hasAttribute("loopNode") && castedNode.getEndNode().getAttribute("loopNode").equals(loopNode)))
				return castedNode;
		}	
		
		// Continue walking through the graph
		List<Edge> outgoingEdges = lookupGraph.getOutgoingEdges(currentNode, EdgeType.Control);
		Node returnValue = null;
		for (Edge e : outgoingEdges) {
			newGraph.addEdge(e);
			Node tempVal = createLoopConstructContents(loopNode, e.getEnd(), newGraph, lookupGraph, visitedNodes);
			if (tempVal != null)
				returnValue = tempVal;
		}

		return returnValue;
	}	
	
	/**
	 * Creates a loop construct for a loop construct in which the condition is evaluated before execution of the loop branch
	 * @param condNode Conditional node
	 * @param graph Original graph
	 * @param visitedNodes List with visited nodes
	 * @return The loop construct
	 * @throws AnalysisException When an exception occurs, AnalysisException will be thrown
	 */
	private Node createLoopConstructPreEvaluation(LoopConditionalNode condNode, Graph graph, List<Node> visitedNodes) throws AnalysisException {
		LoopConstruct construct = new LoopConstruct(condNode.getName() + "_loop");
		construct.setConditionNode(condNode);
		construct.setEvaluateConditionBefore(true);
		
		// Get outgoing edges
		List<Edge> outgoingEdges = graph.getOutgoingEdges(condNode, EdgeType.Control);
		
		Node branchStartNode = null;
		Node followUpNode = null;
		
		// Select the start node of the loop branch and the node after the loop branch 
		if (outgoingEdges.size() == 2) {
			Edge e1 = outgoingEdges.get(0);
			Edge e2 = outgoingEdges.get(1);
			boolean e1IsBranch = isLoopBranch(e1.getEnd(), graph, condNode, new ArrayList<Node>());
			boolean e2IsBranch = isLoopBranch(e2.getEnd(), graph, condNode, new ArrayList<Node>());
			
			if (e1IsBranch && !e2IsBranch) {
				branchStartNode = e1.getEnd();
				followUpNode = e2.getEnd();
			} else if (!e1IsBranch && e2IsBranch) {
				branchStartNode = e2.getEnd();
				followUpNode = e1.getEnd();			
			} else
				throw new AnalysisException("Error during creation of loop construct, none or both of the branches contain loop end");
			
			// Remove the edges from the graph
			graph.removeEdge(e1);
			graph.removeEdge(e2);
			
			// Create edge to follow up node
			graph.addEdge(new Edge(construct, followUpNode, EdgeType.Control));
		} else if (outgoingEdges.size() == 1) {
			Edge e1 = outgoingEdges.get(0);
			branchStartNode = e1.getEnd();
			if (!isLoopBranch(branchStartNode, graph, condNode, new ArrayList<Node>()))
				throw new AnalysisException("Node is not part of a loop branch");
			// Remove edge
			graph.removeEdge(e1);
		} else
			throw new AnalysisException("A loop node should have two outgoing edges, " + outgoingEdges.size() + " found");
		
		Node endNode = createLoopConstructContents(condNode.getName(), branchStartNode, construct.getInnerGraph(), graph, visitedNodes);
		
		// Remove loop edge
		graph.removeEdge(graph.findEdge(endNode, condNode, EdgeType.Control));
		
		// Remove old node and replace with construct
		graph.removeNode(condNode);
		graph.addNode(construct);
		
		// Remove nodes and edges that are moved to composite loop construct from original graph
		for (Node n : construct.getInnerGraph().getNodes())
			graph.removeNode(n);
		for (Edge e : construct.getInnerGraph().getEdges())
			graph.removeEdge(e);			
		
		// Update incoming edges
		for (Edge e : graph.getIncomingEdges(condNode, EdgeType.Control))
			e.setEnd(construct);
		
		// Update outgoing edges
		for (Edge e : graph.getOutgoingEdges(endNode, EdgeType.Control))
			e.setStart(construct);		
		
		// Add contents to graphs list
		this.graphQueue.add(construct.getInnerGraph());
		
		return construct;
	}
	
	/**
	 * Creates a loop construct for a loop construct in which the condition is evaluated after execution of the loop branch
	 * @param firstNode First node of a loop branch
	 * @param graph Original graph
	 * @param visitedNodes List with visited nodes
	 * @return The loop construct
	 * @throws AnalysisException When an exception occurs, AnalysisException will be thrown
	 */
	private Node createLoopConstructPostEvaluation(Node firstNode, Graph graph, List<Node> visitedNodes) throws AnalysisException {
		LoopConstruct construct = new LoopConstruct("");
		construct.setEvaluateConditionBefore(false);
		
		// Create branch and find conditional node
		LoopConditionalNode condNode = (LoopConditionalNode)createLoopConstructContents((String)firstNode.getAttribute("loopNode"), firstNode, construct.getInnerGraph(), graph, new ArrayList<Node>());
		construct.setName(condNode.getName() + "_loop");
		construct.setConditionNode(condNode);
		
		// Remove loop edge
		graph.removeEdge(graph.findEdge(condNode, firstNode, EdgeType.Control));
		
		// Add new node to graph
		graph.addNode(construct);
		
		// Remove nodes and edges that are moved to composite loop construct from original graph
		for (Node n : construct.getInnerGraph().getNodes())
			graph.removeNode(n);
		for (Edge e : construct.getInnerGraph().getEdges())
			graph.removeEdge(e);			
		
		// Remove conditional node from new graph (including incoming edges)
		construct.getInnerGraph().removeNode(condNode);	
		for (Edge e : construct.getInnerGraph().getIncomingEdges(condNode, EdgeType.Control))
			construct.getInnerGraph().removeEdge(e);	
		
		// Update incoming edges
		for (Edge e : graph.getIncomingEdges(firstNode, EdgeType.Control))
			e.setEnd(construct);
		
		// Update outgoing edges
		for (Edge e : graph.getOutgoingEdges(condNode, EdgeType.Control))
			e.setStart(construct);
		
		// Add contents to graphs list
		this.graphQueue.add(construct.getInnerGraph());		
		
		// Add node to finished list, to ensure that the algorithm will not search for the loop again when looking at another graph
		finishedStartNodes.add(firstNode);
			
		return construct;
	}
	
	/**
	 * Checks if the current branch is a loop branch
	 * @param currentNode Current node
	 * @param graph Look up graph
	 * @param loopNode The loop node that should be found
	 * @param visitedNodes List with visited nodes, used for ensuring that no infinite loops can occur.
	 * @return True, if the current branch is a loop branch
	 */
	private boolean isLoopBranch(Node currentNode, Graph graph, LoopConditionalNode loopNode, List<Node> visitedNodes) {
		if (visitedNodes.contains(currentNode))
			return false;
		else
			visitedNodes.add(currentNode);
		
		// Check if the current node, or start/endnode of a branched construct contain the node that should be matched
		if (currentNode == loopNode)
			return true;
		
		if (currentNode instanceof BranchedConstruct<?, ?>) {
			BranchedConstruct<?, ?> castedNode = (BranchedConstruct<?, ?>)currentNode;
			
			if (castedNode.getStartNode().hasAttribute("loopNode") && ((String)castedNode.getStartNode().getAttribute("loopNode")).equals(loopNode.getName()))
				return true;
			if (castedNode.getEndNode().hasAttribute("loopNode") && ((String)castedNode.getEndNode().getAttribute("loopNode")).equals(loopNode.getName()))
				return true;
		}
		
		// Follow outgoing edges
		List<Edge> outgoingEdges = graph.getOutgoingEdges(currentNode, EdgeType.Control);
		for (Edge e : outgoingEdges) {
			if (isLoopBranch(e.getEnd(), graph, loopNode, visitedNodes))
				return true;
		}
		return false;
	}

}